#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 配置参数
#define HASH_TABLE_SIZE 10007
#define MAX_PIXELS 10000
#define MAX_LINE_LENGTH 100

// 哈希表节点结构
typedef struct HashNode {
    int r, g, b;//颜色值
    int count;//出现次数
    struct HashNode *next;//解决哈希冲突的链表
} HashNode;

void generate_test_file(const char* filename);

// ==================== 工具函数 ====================

//两个内存管理函数：safe_malloc、safe_calloc
void* safe_malloc(size_t size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        printf("Error: Memory allocation failed\n");
        exit(1);
    }
    return ptr;
}

void* safe_calloc(size_t num, size_t size) {
    void *ptr = calloc(num, size);
    if (ptr == NULL) {
        printf("Error: Memory allocation failed\n");
        exit(1);
    }
    return ptr;
}

// 哈希函数
unsigned int hash_function(int r, int g, int b) {
    unsigned int hash = (r * 73856093) ^ (g * 19349663) ^ (b * 83492791);
    return hash % HASH_TABLE_SIZE;
}

// ==================== 文件读取 ====================

// 从文件读取图像数据
int read_image_from_file(const char* filename, int*** pixels_ptr, int* pixel_count) {//文件读取函数
    printf("Reading image from: %s\n", filename);
    
    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        printf("Error: Cannot open file %s\n", filename);
        return 0;
    }
    
    // 临时存储像素
    int** temp_pixels = (int**)safe_malloc(MAX_PIXELS * sizeof(int*));
    int count = 0;
    char line[MAX_LINE_LENGTH];
    
    while (fgets(line, sizeof(line), file) != NULL && count < MAX_PIXELS) {
        // 跳过注释和空行
        if (line[0] == '#' || line[0] == '\n' || line[0] == '\r') {
            continue;
        }
        
        int r, g, b;
        if (sscanf(line, "%d %d %d", &r, &g, &b) == 3) {
            // 验证颜色值
            if (r >= 0 && r <= 255 && g >= 0 && g <= 255 && b >= 0 && b <= 255) {
                temp_pixels[count] = (int*)safe_malloc(3 * sizeof(int));
                temp_pixels[count][0] = r;
                temp_pixels[count][1] = g;
                temp_pixels[count][2] = b;
                count++;
            }
        }
    }
    
    fclose(file);
    
    if (count == 0) {
        printf("No valid pixels found in file\n");
        for (int i = 0; i < count; i++) {
            free(temp_pixels[i]);
        }
        free(temp_pixels);
        return 0;
    }
    
    // 分配精确大小的数组
    int** pixels = (int**)safe_malloc(count * sizeof(int*));
    for (int i = 0; i < count; i++) {
        pixels[i] = temp_pixels[i];
    }
    free(temp_pixels);
    
    *pixels_ptr = pixels;
    *pixel_count = count;
    
    printf("Successfully read %d pixels\n", count);
    return 1;
}

// ==================== 哈希表统计 ====================

void histogram_hash(int** pixels, int pixel_count) {
    printf("\nCalculating histogram...\n");
    
    // 创建哈希表
    HashNode** hash_table = (HashNode**)safe_calloc(HASH_TABLE_SIZE, sizeof(HashNode*));
    
    int unique_colors = 0;
    int max_count = 0;
    int max_r = 0, max_g = 0, max_b = 0;
    
    // 统计颜色
    for (int i = 0; i < pixel_count; i++) {
        int r = pixels[i][0];
        int g = pixels[i][1];
        int b = pixels[i][2];
        
        unsigned int index = hash_function(r, g, b);
        
        HashNode* current = hash_table[index];
        HashNode* prev = NULL;
        int found = 0;
        
        // 查找颜色
        while (current != NULL) {
            if (current->r == r && current->g == g && current->b == b) {
                current->count++;
                if (current->count > max_count) {
                    max_count = current->count;
                    max_r = r;
                    max_g = g;
                    max_b = b;
                }
                found = 1;
                break;
            }
            prev = current;
            current = current->next;
        }
        
        // 添加新颜色
        if (!found) {
            HashNode* new_node = (HashNode*)safe_malloc(sizeof(HashNode));
            new_node->r = r;
            new_node->g = g;
            new_node->b = b;
            new_node->count = 1;
            new_node->next = NULL;
            
            if (prev == NULL) {
                hash_table[index] = new_node;
            } else {
                prev->next = new_node;
            }
            
            unique_colors++;
            
            if (1 > max_count) {
                max_count = 1;
                max_r = r;
                max_g = g;
                max_b = b;
            }
        }
    }
    
    // 输出结果
    printf("\n=== Results ===\n");
    printf("Total pixels: %d\n", pixel_count);
    printf("Unique colors: %d\n", unique_colors);
    printf("Most frequent color: RGB(%d, %d, %d)\n", max_r, max_g, max_b);
    printf("Count: %d (%.1f%%)\n", max_count, (float)max_count / pixel_count * 100);
    
    // 释放哈希表
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        HashNode* current = hash_table[i];
        while (current != NULL) {
            HashNode* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(hash_table);
}

// ==================== 内存释放 ====================

void free_pixels(int** pixels, int count) {
    if (pixels == NULL) return;
    
    for (int i = 0; i < count; i++) {
        if (pixels[i] != NULL) {
            free(pixels[i]);
        }
    }
    free(pixels);
}

// ==================== 主函数 ====================

int main() {
    printf("=== Color Histogram ===\n");
    
    const char* filename = "image_data.txt";//确保测试文件已经创建
    int** pixels = NULL;
    int pixel_count = 0;
    
    // 尝试读取文件
    if (!read_image_from_file(filename, &pixels, &pixel_count)) {
        printf("Error: Cannot read image data from %s\n", filename);
        printf("Please create a file named '%s' with RGB data.\n", filename);
        printf("Format: R G B (one pixel per line, values 0-255)\n");
        printf("Example:\n");
        printf("255 0 0\n");
        printf("0 255 0\n");
        printf("0 0 255\n");
        return 1;
    }
    
    // 计算直方图
    histogram_hash(pixels, pixel_count);
    
    // 清理内存
    free_pixels(pixels, pixel_count);
    
    printf("\nDone!\n");
    return 0;
}